The display, transmission and storage of visual images is increasingly important for modern communications. In particular, it is important for modern computer driven displays to receive, transmit, store and display sequences of images in rapid succession such as is shown in movies. The quality of the visual display can be improved by representing the visual images in a digital format. Generally, a visual image can be represented by dividing the image into sufficiently small picture elements, called pixels, and assigning to each pixel a color and a value representing the intensity of the color for the pixel. For example, a typical 8 inch by 10 inch visual image may be divided into a two dimensional array of 768 by 1024 pixels wherein each pixel is further divided into 3 subpixels. The three subpixels are each associated with one of the three primary colors red, green, or blue. Each subpixel is assigned a digital value corresponding to the intensity level for the color of the subpixel. The subpixels are small enough such that the human eye does not resolve each subpixel. Rather, the image presented by a pixel to the viewer is some combination of the three colors associated with each subpixel weighted by the intensity value for each subpixel color. As a result, the visual image is represented by three two dimensional matrices of color intensity values.
This digital image represents a high quality image because the pixels are small. However, as the pixel gets smaller, there are more pixels for the same size image and more intensity values to store, manipulate, and transmit. The fact that more pixels requires more data also results in a reduction in the ability to transmit images because the amount of data for each image transmitted is so large. As a result, various efforts have been made to transform the Red Green Blue (RGB) data into another form of data which can be transmitted and stored efficiently and which can also be re-transformed back into RGB data for display. The new form of data most often chosen relates the RGB data to a luminance value and two chrominance values. In particular, the luminance value represents the intensity of a pixel on a grey scale which provides an accurate representation of the image to a monochrome display. The luminance value is obtained by weighting each intensity value of the RGB data and combining them. For example, the National Television Systems Committee (NTSC) standard luminance value Y=0.299R+0.587G+0.114B, wherein R is the red intensity value, G is the green intensity value, and B is the blue intensity value. The two chrominanace values convey information which describes how the colors differ from monochrome. For example, the NTSC values are U=Y-B and V=Y-R. The RGB to YUV transform compacts most of the visual intensity information into the luminance variable. This effect is similar to viewing a color image on a monochrome monitor in that the viewer understands a significant portion of the image but does not understand it all. This effect is useful for reducing the amount of data representing the image because the YUV data can be digitally filtered and coded such that much of the chrominance data, and some of the luminance data, can be discarded and replaced with code values. There are a variety of techniques for performing the filtering process, the most common of which is a Discrete Cosine Transform (DCT). The DCT replaces local blocks of YUV pixel data (typically 8.times.8 pixels) with data generated from the YUV to DCT conversion performed on the YUV data. The resulting DCT data may then be quantized and coded, yielding a very compact representation which can be easily stored or transmitted.
The storage and transmission of coded and quantized DCT data is efficient because there is much less data volume than would be the case for storing or transmitting the full YUV or RGB image data. The visual image represented by the DCT data can be reconstructed at the point of visual display (or use) by inverting the coding, YUV, and DCT processes and applying these inverted processes to the DCT data to yield RGB image data. These coding, YUV, and DCT processes are largely, but not exactly invertable. More specifically, the quantization process is not completely invertable because it contains a data truncation step and the part of the data which is lost by the truncation is not recoverable. Nevertheless, the inversion processes re-convert the DCT data into a visual image which is visually indistinguishable from the original image. The problem with these inversion processes, however, is that many applications of digital image processing require the reconstructed image to be of a size which is not identical to the original image. That is, the reconstruction must be scaled, either up or down, with respect to the original image. This is a problem with the process of merely inverting the DCT processes because this process generates a 1:1 scaled image of the original image which then must be separately scaled to the desired size. The scaling process on top of the inverted DCT processes require many mathematical operations. More particularly, they require many non-trivial multiplications which require a substantial amount of computer processor time to complete. This processor time must be spent on each pixel of each image processed, and so much computer processor time is used when scaling the image that the rate at which the images may be displayed is degraded. Degrading the display rate degrades the ability to display objects in motion. As a result, either the speed at which the processor multiplies must be increased or the scaling process must be changed to require fewer arithmetic operations in order to implement high quality motion displays.
One prior art attempt at increasing the speed of the multiplications is to replace the multiplication operations with look up tables. Look up tables may reduce the time required for multiplication operations which often are much slower than additions or subtractions because multiplications in the binary number system are typically a series of bit shift and add operations so that the time for each multiplication is a multiple of an add operation. Also, look-up tables are convenient to implement whereas special purpose multiplication hardware is much more complex than special purpose fixed point addition, subtraction and shift hardware. However, even though a look up table decreases the number of multiplication operations, they can still be rather slow. Moreover, many computer processors are very efficient in using time between multiplications when performing many multiplications because of the pipelined structure of the processor. When look up tables are used in conjunction with computer processors, the pipelined structure can be disrupted and the overall efficiency of image processing is decreased even though the individual look up table operation is faster than the multiplication operation. Therefore, look up tables have not been very successful in increasing the speed of the image processing.
Beyond inproving the speed of the multiplication operation, the prior art has also attempted to reduce the number of arithmetic operations required for scaling. Scaling involves filtering. Filtering involves multiplications and additions and/or subtractions. Reducing the number of arithmetic operations in the filtering process often has the effect of degrading the visual quality of the scaled image. The prior art has also attempted to adjust the scaling process by direct scaling with modified inverse DCT processes. For example, an image coded with P.times.P blocks subjected to P.times.P DCTs is decoded with inverse DCTs of size Q.times.Q. If Q.ltoreq.P, then the leading (top left) Q.times.Q majors of the P.times.P DCT components are subjected to the inverse Q.times.Q DCT. If Q.gtoreq.P, then the P.times.P block of DCT components is padded with 0's on the right and bottom, and the resulting larger block is subjected to a Q.times.Q inverse DCT. In either case, the result is an image scaled by factor Q/P in each dimension. The problem with this scaling technique is that it is only valid for a very constrained set of possible scaling ratios. For example, an image processed with 8.times.8 DCTs cannot be scaled to a factor 1/3 or a factor 2/3 using this method.